All Questions
19 questions
6votes
1answer
393views
Condition Number dependent algorithms for matrix operations
Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
- 958
3votes
2answers
424views
What is the best approximation and exact algorithm for vertex cover on cubic graphs?
"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
- 41
3votes
1answer
63views
Complexity of distributively verifying that the diameter is small
Consider a graph $G=(V,E)$ and an integer parameter $k$. I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ...
- 9,548
1vote
0answers
50views
Sparse coding and matching pursuit algorithms
Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the ...
- 1,463
5votes
0answers
218views
On permanent of $\{\pm1,0\}$ matrices
Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|<B$ where $B$ is part of input. Is ...
- 13.5k
5votes
1answer
153views
Does k-PATH admit a constant approximation?
In the $k$-PATH problem, we receive as input a graph $G$ and an integer $k$. The goal is to decide whether there exists a simple path of length $k$ in $G$. A $\alpha$-approximation for $k$-PATH is an ...
- 51
5votes
0answers
247views
Maximizing the number of selected edges with opposing requirements
Consider the following problem: Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$. Output: a subset of vertices $W$ of size $k$ which maximizes the ...
6votes
0answers
184views
Statistical Algorithms vs Convex Relaxations - Planted Clique
I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ? A recent paper by Feldman, ...
- 666
12votes
2answers
1kviews
What is this variant of set cover problem known as?
Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$. An incremental ...
- 221
4votes
1answer
238views
Polynomial-time distinguishability threshold of planted clique
I have a basic question regarding the best known polynomial-time "distinguishing advantage" for the planted clique problem. By this, I'm referring to the problem of distinguishing the distribution $G(...
- 623
3votes
2answers
438views
Set packing with maximum coverage objective
We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. Set-Packing asks how many disjoint sets we can pack, and is defined ...
- 9,548
0votes
1answer
662views
FPTAS for Number Partition Problem
I've been given a task to implement two algorithms (an exact algorithm and fully polynomial approximation scheme) for number partitioning problem. I found out that I can use some modification of ...
4votes
1answer
1kviews
Path coloring in general graphs
Path coloring is the problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors. We know that coloring a set of paths ...
- 1,601
6votes
2answers
241views
Vertex subset of maximum size
I was wondering if this problem has a name and/or it has been already studied. Problem: Given an undirected graph $G=(V,E)$, a function $f: V \to \mathbb N$, and a natural number $k$ : Does ...
- 61
15votes
1answer
503views
Imperfect subgraph isomorphism
Consider the following problem: Given a query graph $G = (V, E)$ and a reference graph $G' = (V', E')$, we want to find the injective mapping $f : V \rightarrow V'$ which minimizes the number of edges ...
